use crate::stools::{random_array, random_num};
use std::cmp::min;

/// 在n个位置的坐标上，机器人从s到e，用rest步一共有多少种走法
fn walk_ways(n: usize, e: usize, rest: usize, s: usize) -> usize {
    if rest == 0 {
        return if s == e { 1 } else { 0 };
    }
    if s == 0 {
        return walk_ways(n, e, rest - 1, s + 1);
    }
    if s == n - 1 {
        return walk_ways(n, e, rest - 1, s - 1);
    }

    return walk_ways(n, e, rest - 1, s + 1) + walk_ways(n, e, rest - 1, s - 1);
}

/// 机器人运动问题
/// 在一个[0, N)的N个位置的一维坐标上，机器人从S开始step步走到E坐标一共有多少种走法
fn find_walk_ways(n: usize, e: usize, step: usize, s: usize) -> usize {
    if n == 0 || s + step < e {
        return 0;
    }
    return walk_ways(n, e, step, s);
}
fn walk_ways_mem(
    n: usize,
    e: usize,
    dp: &mut Vec<Vec<Option<usize>>>,
    rest: usize,
    s: usize,
) -> Option<usize> {
    if rest == 0 {
        dp[rest][s] = if s == e { Some(1) } else { Some(0) };
        return dp[rest][s];
    }
    if s == 0 {
        return walk_ways_mem(n, e, dp, rest - 1, s + 1);
    }
    if s == n - 1 {
        return walk_ways_mem(n, e, dp, rest - 1, s - 1);
    }

    return Some(
        walk_ways_mem(n, e, dp, rest - 1, s + 1).unwrap()
            + walk_ways_mem(n, e, dp, rest - 1, s - 1).unwrap(),
    );
}

fn find_walk_ways_mem(n: usize, e: usize, step: usize, s: usize) -> usize {
    if n == 0 || s + step < e {
        return 0;
    }

    let mut dp: Vec<Vec<Option<usize>>> = vec![vec![None; n + 1]; step + 1];

    return walk_ways_mem(n, e, &mut dp, step, s).unwrap();
}

/// 从arr[idx..]中组合出rest面值用多少硬币
fn min_coins_recursion(arr: &[i32], idx: usize, rest: i32) -> i32 {
    if rest < 0 {
        return -1;
    }
    if rest == 0 {
        return 0;
    }
    // rest > 0
    if idx == arr.len() {
        return -1;
    }

    let p1 = min_coins_recursion(arr, idx + 1, rest);
    let p2 = min_coins_recursion(arr, idx + 1, rest - arr[idx]);
    match (p1, p2) {
        (-1, -1) => -1,
        (-1, _) => 1 + p2,
        (_, -1) => p1,
        (_, _) => min(p1, 1 + p2),
    }
}

/// 一个正数数组表示多个面值的硬币，对于给定的目标aim，计算组成aim最少用多少枚硬币
/// 比如：arr: [2, 3, 100], aim = 5
fn fmin_coins_recursion(arr: &[i32], aim: i32) -> i32 {
    min_coins_recursion(arr, 0, aim)
}

/// 从arr[idx..]中组合出rest面值用多少硬币
fn min_coins_mem(arr: &[i32], idx: usize, rest: i32, dp: &mut Vec<Vec<i32>>) -> i32 {
    if rest < 0 {
        return -1;
    }

    if dp[idx][rest as usize] != -2 {
        return dp[idx][rest as usize];
    }

    if rest == 0 {
        dp[idx][rest as usize] = 0;
        return dp[idx][rest as usize];
    }
    // rest > 0
    if idx == arr.len() {
        dp[idx][rest as usize] = -1;
        return dp[idx][rest as usize];
    }

    let p1 = min_coins_recursion(arr, idx + 1, rest);
    let p2 = min_coins_recursion(arr, idx + 1, rest - arr[idx]);
    dp[idx][rest as usize] = match (p1, p2) {
        (-1, -1) => -1,
        (-1, _) => 1 + p2,
        (_, -1) => p1,
        (_, _) => min(p1, 1 + p2),
    };

    dp[idx][rest as usize]
}

fn fmin_coins_mem(arr: &[i32], aim: i32) -> (i32, Vec<Vec<i32>>) {
    let mut dp: Vec<Vec<i32>> = vec![vec![-2; aim as usize + 1]; arr.len() + 1];
    let coins = min_coins_mem(arr, 0, aim, &mut dp);
    (coins, dp)
}

fn fmin_coins_dp(arr: &[i32], aim: i32) -> (i32, Vec<Vec<i32>>) {
    let mut dp: Vec<Vec<i32>> = vec![vec![-2; aim as usize + 1]; arr.len() + 1];
    for idx in 0..=arr.len() {
        dp[idx][0] = 0;
    }
    for rest in 1..=aim {
        dp[arr.len()][rest as usize] = -1;
    }

    for idx in (0..arr.len()).rev() {
        for rest in (1..=aim as usize).rev() {
            let p1 = dp[idx + 1][rest as usize];
            let mut p2 = -1;
            if rest >= arr[idx] as usize {
                p2 = dp[idx + 1][rest - arr[idx] as usize];
            }
            dp[idx][rest] = match (p1, p2) {
                (-1, -1) => -1,
                (-1, _) => 1 + p2,
                (_, -1) => p1,
                (_, _) => min(p1, 1 + p2),
            };
        }
    }
    (dp[0][aim as usize], dp)
}

const N: i32 = 9;
const M: i32 = 10;
/// 从(0, 0) 经过 step 到 (x, y) 有几种方法
fn horse_walkways_recursion(x: i32, y: i32, step: usize) -> usize {
    if x >= N || y >= M || x < 0 || y < 0 {
        return 0;
    }

    if step == 0 {
        return if x == 0 && y == 0 { 1 } else { 0 };
    }

    horse_walkways_recursion(x - 1, y + 2, step - 1)
        + horse_walkways_recursion(x + 1, y + 2, step - 1)
        + horse_walkways_recursion(x - 2, y + 1, step - 1)
        + horse_walkways_recursion(x + 2, y + 1, step - 1)
        + horse_walkways_recursion(x + 2, y - 1, step - 1)
        + horse_walkways_recursion(x - 2, y - 1, step - 1)
        + horse_walkways_recursion(x + 1, y - 2, step - 1)
        + horse_walkways_recursion(x - 1, y - 2, step - 1)
}

/// 9x10的棋盘，马在(0, 0)处，经过k步到(a, b)有几种走法
fn get_horse_walkways_recursion(a: i32, b: i32, step: usize) -> usize {
    horse_walkways_recursion(a, b, step)
}

/// 从(0, 0) 经过 step 到 (x, y) 有几种方法
fn horse_walkways_mem(x: i32, y: i32, step: usize, dp: &mut Vec<Vec<Vec<i32>>>) -> usize {
    if x >= N || y >= M || x < 0 || y < 0 {
        return 0;
    }

    if dp[step][x as usize][y as usize] != -1 {
        return dp[step][x as usize][y as usize] as usize;
    }

    if step == 0 {
        dp[step][x as usize][y as usize] = if x == 0 && y == 0 { 1 } else { 0 };
        return dp[step][x as usize][y as usize] as usize;
    }

    horse_walkways_mem(x - 1, y + 2, step - 1, dp)
        + horse_walkways_mem(x + 1, y + 2, step - 1, dp)
        + horse_walkways_mem(x - 2, y + 1, step - 1, dp)
        + horse_walkways_mem(x + 2, y + 1, step - 1, dp)
        + horse_walkways_mem(x + 2, y - 1, step - 1, dp)
        + horse_walkways_mem(x - 2, y - 1, step - 1, dp)
        + horse_walkways_mem(x + 1, y - 2, step - 1, dp)
        + horse_walkways_mem(x - 1, y - 2, step - 1, dp)
}

/// 9x10的棋盘，马在(0, 0)处，经过k步到(a, b)有几种走法
fn get_horse_walkways_mem(a: i32, b: i32, step: usize) -> usize {
    let mut dp: Vec<Vec<Vec<i32>>> = vec![vec![vec![-1; M as usize]; N as usize]; step + 1];
    horse_walkways_mem(a, b, step, &mut dp)
}

fn get_value(dp: &mut Vec<Vec<Vec<usize>>>, rest: i32, x: i32, y: i32) -> usize {
    if x < 0 || y < 0 || rest < 0 || x >= N || y >= M {
        return 0;
    }

    return dp[rest as usize][x as usize][y as usize];
}

/// 9x10的棋盘，马在(0, 0)处，经过k步到(a, b)有几种走法
fn get_horse_walkways_dp(a: i32, b: i32, step: i32) -> usize {
    let mut dp: Vec<Vec<Vec<usize>>> =
        vec![vec![vec![0; M as usize]; N as usize]; step as usize + 1];
    dp[0][0][0] = 1;

    for rest in 1..=step {
        for x in 0..N {
            for y in 0..M {
                dp[rest as usize][x as usize][y as usize] =
                    get_value(&mut dp, rest - 1, x - 1, y + 2)
                        + get_value(&mut dp, rest - 1, x + 1, y + 2)
                        + get_value(&mut dp, rest - 1, x - 2, y + 1)
                        + get_value(&mut dp, rest - 1, x + 2, y + 1)
                        + get_value(&mut dp, rest - 1, x + 2, y - 1)
                        + get_value(&mut dp, rest - 1, x - 2, y - 1)
                        + get_value(&mut dp, rest - 1, x + 1, y - 2)
                        + get_value(&mut dp, rest - 1, x - 1, y - 2);
            }
        }
    }

    dp[step as usize][a as usize][b as usize]
}

/// bob在(x, y)处走rest步，能生存的走法
fn bob_live_recursion(m: usize, n: usize, x: i32, y: i32, rest: i32) -> usize {
    if x < 0 || x >= m as i32 || y < 0 || y >= n as i32 {
        return 0;
    }

    if rest == 0 {
        return 1;
    }

    bob_live_recursion(m, n, x - 1, y, rest - 1)
        + bob_live_recursion(m, n, x + 1, y, rest - 1)
        + bob_live_recursion(m, n, x, y + 1, rest - 1)
        + bob_live_recursion(m, n, x, y - 1, rest - 1)
}

fn gcd(mut a: usize, mut b: usize) -> usize {
    while a % b != 0 {
        b = a % b;
        a = b;
    }
    b
}

/// 在一个MxN的棋盘中，Bob在(x, y)处等概率上下左右运动，走k步后生成的概率
fn bob_live_probability_recrusion(m: usize, n: usize, x: usize, y: usize, step: usize) -> String {
    let alive = bob_live_recursion(m, n, x as i32, y as i32, step as i32);
    let mv = 4i32.pow(step as u32);
    let gcd = gcd(alive, mv as usize);
    format!("{} / {}", alive / gcd, mv as usize / gcd)
}

/// 从arr[idx..]中选出rest面值有多少种方法
fn aim_coins_recursion(arr: &[usize], idx: usize, rest: i32) -> usize {
    if rest < 0 {
        return 0;
    }
    if idx == arr.len() {
        return if rest == 0 { 1 } else { 0 };
    }

    let mut methods = 0;
    for num in 0.. {
        if num * arr[idx] > rest as usize {
            break;
        }
        methods += aim_coins_recursion(arr, idx + 1, rest - (num * arr[idx]) as i32);
    }
    methods
}

/// 正数硬币数组，同种币值可选任意次，达到aim面值有多少种方法
fn get_aim_coins_recursion(arr: &[usize], aim: i32) -> usize {
    aim_coins_recursion(arr, 0, aim)
}

/// 从arr[idx..]中选出rest面值有多少种方法
fn aim_coins_mem(arr: &[usize], idx: usize, rest: i32, dp: &mut Vec<Vec<i32>>) -> usize {
    if dp[idx][rest as usize] != -1 {
        return dp[idx][rest as usize] as usize;
    }

    if rest < 0 {
        return 0;
    }
    if idx == arr.len() {
        dp[idx][rest as usize] = if rest == 0 { 1 } else { 0 };
        return dp[idx][rest as usize] as usize;
    }

    dp[idx][rest as usize] = 0;
    for num in 0.. {
        if num * arr[idx] > rest as usize {
            break;
        }
        dp[idx][rest as usize] +=
            aim_coins_mem(arr, idx + 1, rest - (num * arr[idx]) as i32, dp) as i32;
    }
    dp[idx][rest as usize] as usize
}

/// 正数硬币数组，同种币值可选任意次，达到aim面值有多少种方法
fn get_aim_coins_mem(arr: &[usize], aim: i32) -> usize {
    let mut dp: Vec<Vec<i32>> = vec![vec![-1; aim as usize + 1]; arr.len() + 1];
    aim_coins_mem(arr, 0, aim, &mut dp)
}

/// 正数硬币数组，同种币值可选任意次，达到aim面值有多少种方法
fn get_aim_coins_dp(arr: &[usize], aim: i32) -> usize {
    let mut dp: Vec<Vec<i32>> = vec![vec![0; aim as usize + 1]; arr.len() + 1];
    dp[arr.len()][0] = 1;

    for idx in (0..arr.len()).rev() {
        for rest in 0..=aim as usize {
            for num in 0.. {
                if num * arr[idx] > rest {
                    break;
                }
                dp[idx][rest] += dp[idx + 1][rest - num * arr[idx]];
            }
        }
    }

    dp[0][aim as usize] as usize
}

/// 正数硬币数组，同种币值可选任意次，达到aim面值有多少种方法
fn get_aim_coins_dp_optimize(arr: &[usize], aim: i32) -> usize {
    let mut dp: Vec<Vec<i32>> = vec![vec![0; aim as usize + 1]; arr.len() + 1];
    dp[arr.len()][0] = 1;

    for idx in (0..arr.len()).rev() {
        for rest in 0..=aim as usize {
            dp[idx][rest] = dp[idx + 1][rest];
            if rest >= arr[idx] {
                dp[idx][rest] += dp[idx][rest - arr[idx]];
            }
        }
    }

    dp[0][aim as usize] as usize
}

pub fn violence_main() {
    println!("============ 机器人运动问题 ============");
    let n: usize = random_num(0..11);
    let s: usize = random_num(0..n / 2);
    let e: usize = random_num(0..n);
    let step: usize = random_num(0..n);
    println!(
        "机器人在[0, {})的坐标上，经{}步从{}到{}共有{}种走法",
        n,
        step,
        s,
        e,
        find_walk_ways(n, e, step, s)
    );
    println!(
        "机器人在[0, {})的坐标上，经{}步从{}到{}共有{}种走法",
        n,
        step,
        s,
        e,
        find_walk_ways_mem(n, e, step, s)
    );

    println!("============ 最少硬币问题 ============");
    println!("从不同面值的硬币arr中组成目标面值aim，最少用多少硬币");
    let arr = random_array(10, 0..20);
    let aim = random_num(0..100);
    println!(
        "[暴力递归] 从{:?}中组合出面值{}最少用{}枚硬币",
        arr,
        aim,
        fmin_coins_recursion(&arr, aim)
    );

    let (coins, _dp) = fmin_coins_mem(&arr, aim);
    println!(
        "[记忆搜索] 从{:?}中组合出面值{}最少用{}枚硬币",
        arr, aim, coins
    );

    let (coins, _dp) = fmin_coins_dp(&arr, aim);
    println!(
        "[动态规划] 从{:?}中组合出面值{}最少用{}枚硬币",
        arr, aim, coins
    );

    println!("============ 马走象棋 ============");
    println!("在9x10的棋盘棋盘上，马从(0, 0)经k步走到(a, b)一共有多少种走法");
    let arr = [
        (1, 1, 2),
        (2, 2, 0),
        (3, 4, 1),
        (4, 5, 3),
        (5, 3, 4),
        (6, 2, 2),
    ];
    for (step, a, b) in arr {
        println!(
            "[递归搜索] (0, 0) --{}--> ({}, {}) 有{}种走法",
            step,
            a,
            b,
            get_horse_walkways_recursion(a, b, step)
        );
        println!(
            "[记忆搜索] (0, 0) --{}--> ({}, {}) 有{}种走法",
            step,
            a,
            b,
            get_horse_walkways_mem(a, b, step)
        );
        println!(
            "[动态规划] (0, 0) --{}--> ({}, {}) 有{}种走法",
            step,
            a,
            b,
            get_horse_walkways_dp(a, b, step as i32)
        );
    }
    println!("============ Bob的生存概率 ============");
    println!("在m x n的棋盘棋盘上，Bob从(0, 0)走k步后仍然生存的概率是多少？");
    let m = random_num(2..7);
    let n = random_num(2..7);
    let step = random_num(4..10);
    let x = random_num(0..m);
    let y = random_num(0..n);
    println!(
        "在{}x{}的棋盘上，bob从({}, {})开始走{}步生存概率：{:?}",
        m,
        n,
        x,
        y,
        step,
        bob_live_probability_recrusion(m, n, x, y, step)
    );

    println!("============ 硬币问题 ============");
    println!("正数硬币数组，同种币值可选任意次，达到aim面值有多少种方法");
    let arr: Vec<usize> = random_array(5, 1..10);
    let aim = random_num(1..50);
    println!(
        "[递归选择] 从{:?}中选出{}面值的硬币有{}种方法",
        arr,
        aim,
        get_aim_coins_recursion(&arr, aim)
    );
    println!(
        "[记忆搜索] 从{:?}中选出{}面值的硬币有{}种方法",
        arr,
        aim,
        get_aim_coins_mem(&arr, aim)
    );
    println!(
        "[动态规划] 从{:?}中选出{}面值的硬币有{}种方法",
        arr,
        aim,
        get_aim_coins_dp(&arr, aim)
    );
    println!(
        "[动规优化] 从{:?}中选出{}面值的硬币有{}种方法",
        arr,
        aim,
        get_aim_coins_dp_optimize(&arr, aim)
    );
}
